1. Field of the Invention
2. Description of Related Art
Video database or video transmission appears as the core of future multi-media technologies. Most visible objects recognized by human beings can be fundamentally represented as a shape and a internal texture. The future video processing technologies aim at processing a unit of an object or its content perceived by human being rather than of a unit of each frame. Particularly, an international image coding standard such as Moving Picture Experts Group 4 (MPEG4) have content-based processing as its main target. Accordingly, a two-dimensional curve coding method has been used as a fundamental means in depicting the image of an object.
In general, the shape of a given two-dimensional curve can be coded by polygonal approximation. Also, the coded curve can be coded once more. For this, an error between an original curve segment and an approximated straight line between two original vertices (hereafter polygon line) should be calculated. Various methods can be applied to an error sampling method for obtaining the error between the original curve and the polygon line. As one example, there is a method for obtaining a distance between one point on the original curve and one point on the polygon line as shown in FIG. 1.
To reduce the amount of coded error values, N samples are taken from a polygon line. The interval between two samples is equivalent to the next interval of two samples. In order to select vertices to make polygon lines, first set two points on an original curve, having maximum distance between them, as two initial vertices. FIG. 2 shows a conventional vertex selection method using a length between an original curve and polygon line. Referring to FIG. 2, if an error between an pixel on a original curve and a pixel on polygon line is more than or equal to a predetermined critical value in the case of vertices A and B, a new vertex is added on the original curve between the two vertices A and B. The aforementioned error is a value obtained by measuring a distance of a pixel on the original curve and the pixel on polygon line between A and B. Here, when a point is set as (x1 and y1) and an equation of a straight line between the vertices A and B is set as `ax+by+c=0`, the vertical distance d can be calculated as follows: ##EQU1##
When the point C has a maximum value d of Equation 1 among all points on the original curve between the vertices A and B and the distance d is greater than or equal to a predetermined critical value, the point C is set as a new vertex. This process is performed on every vertex and repeated until a newly-added vertex does not exist.
In order to remove errors between an original curve and polygon line and get lossless results after coding, all points on the original curve are set as vertices and the vertices should be coded since there are a plurality of intersected points of an original curve with the lines perpendicular to the polygon line in each sample position. However, the coding of every point on the original curve causes degradation of coding efficiency. Particularly, a coder using prediction with respect to information on shape between two frames which are successive in respect of time must predict every point, which is impossible in practice.
In a lossy coding method, an error sampling method as in FIG. 3 is utilized. That is, Equation 1 is applied to each point (x.sub.i,y.sub.i) such as X0, X1, . . . , X8 on an original curve. When an error sampling is performed with respect to the original curve! a denominator of Equation 1 does not need to be calculated again since the polygon line is fixed. However, at least two multiplications (ax.sub.1,by.sub.1), two additions (ax.sub.1 +by.sub.1,by.sub.1 +c) and a division are required, and the amount of calculation is large. Also, when more than one point of the original curve intersects with the lines perpendicular to the polygon line during the error sampling (even in the case of the lossy coding), it is not easy to find a point, which minimally degrades quality from the intersection points. Therefore, it is difficult to design an efficient coder.
When the coded errors are reconstructed into the original image, the positions of A0, A1, . . . , A8 of FIG. 3 should not be changed during coding because coding and decoding must be accomplished on the basis of the polygon line on the basis that there is no information on the original curve during reconstruction. Accordingly, in order to code or decode an error, vertical distances between pre-defined points A0, A1, . . . , A8 on the coded straight line of FIG. 3 and the original curve should be measured instead of using a method of drawing the foot of a perpendicular from the points on the original curve to the coded straight line. For this, intersections of the perpendiculars drawn upward from the A0, A1, . . . , A8 with the original curve are obtained and set as X0, X1, . . . , X8, respectively. Then, the lengths of the perpendiculars drawn upward from the A0, A1, . . . , A8 to the original curve are calculated, thereby obtaining an error suitable for the coding or decoding. However, in such a method, the perpendiculars drawn upward from A0, A1, . . . , A8 may not be correctly consistent with the original curve, thereby lowering the efficiency of coding.